import java.util.*;

/**
 * 554. 砖墙
 * https://leetcode-cn.com/problems/brick-wall/
 */
public class Solutions_554 {
    public static void main(String[] args) {
//        List<List<Integer>> wall = new ArrayList<>();
//        wall.add(Arrays.asList(1, 2, 2, 1));
//        wall.add(Arrays.asList(3, 1, 2));
//        wall.add(Arrays.asList(1, 3, 2));
//        wall.add(Arrays.asList(2, 4));
//        wall.add(Arrays.asList(3, 1, 2));
//        wall.add(Arrays.asList(1, 3, 1, 1));  // output: 2

        List<List<Integer>> wall = new ArrayList<>();
        wall.add(Arrays.asList(1));
        wall.add(Arrays.asList(1));
        wall.add(Arrays.asList(1));  // output: 3

        int result = leastBricks(wall);
        System.out.println(result);
    }

    /**
     * 解题思路：前缀和
     */
    public static int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<>();
        for (List<Integer> list : wall) {
            int preSum = 0;
            // 最后一块“墙”不遍历
            for (int i = 0; i < list.size() - 1; i++) {
                preSum += list.get(i);
                map.put(preSum, map.getOrDefault(preSum, 0) + 1);
            }
        }
        int len = wall.size();
        int res = 0;
        for (int num : map.keySet()) {
            // 记录下最大值
            res = Math.max(res, map.get(num));
        }
        // len - 最大值，即是穿过的砖块数量最少
        return len - res;
    }
}
